
class Solution {
public:
    int findv(vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return left;
        int flag = nums[left];
        int firstMaxIdx = left+1;
        for(int i = left+1; i <= right; i++)
        {
            if(nums[i] < flag)
            {
                swap(nums[i], nums[firstMaxIdx]);
                firstMaxIdx++;
            }
        }
        swap(nums[firstMaxIdx-1], nums[left]);
        return firstMaxIdx-1;
    }

    void qsort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return;
        int mid = findv(nums, left, right);
        qsort(nums, left, mid);
        qsort(nums, mid+1, right);
    }
    int threeSumClosest(vector<int>& nums, int target) {
        if(nums.size()<3)
            return {};
        qsort(nums, 0, nums.size()-1);
        int res = 100000;
        for(int i = 0; i < nums.size()-2; i++)
        {
            int left = i+1;
            int right = nums.size()-1;
            while(left < right)
            {
                int cntSum = nums[left]+nums[right]+nums[i];
                if(abs(cntSum-target) < abs(res-target))
                    res = cntSum;
                if(cntSum == target) return target;
                else if(cntSum > target) right--;
                else if(cntSum < target) left++;
                while(left<right && left>i+1 && nums[left]==nums[left-1]) left++;
                while(left<right && right<nums.size()-1 && nums[right]==nums[right+1]) right--;
            }
            while(i+1<nums.size() && nums[i]==nums[i+1]) i++;
        }

        return res;
    }
};